#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void Print(int* array, int size)
{
  for(int i = 0; i < size; i++){
    printf("%d ", array[i]);
  }
  printf("\n");
}

void Swap(int* pa1, int* pa2)
{
  int sub = *pa1;
  *pa1 = *pa2;
  *pa2 = sub;
}

void _MergeSort(int* array, int left, int right, int* replace)
{
  if(left >= right) return ;

  int mid = (left + right) >> 1;
  _MergeSort(array, left, mid, replace);
  _MergeSort(array, mid + 1, right, replace);

  int begin1 = left;
  int end1 = mid;
  int begin2 = mid + 1;
  int end2 = right;

  int curr = begin1;
  while(begin1 <= end1 && begin2 <= end2){
    //保证稳定性
    if(array[begin1] <= array[begin2]) replace[curr++] = array[begin1++];
    else replace[curr++] = array[begin2++];
  }

  while(begin1 <= end1) {
    replace[curr++] = array[begin1++];
  }

  while(begin2 <= end2){
    replace[curr++] = array[begin2++];
  }

  //只拷贝归并的数据即可i
  // for(int i = left; i <= right; i++){
  //   array[i] = replace[i];
  // }
  memcpy(array + left, replace + left, (right - left + 1) * sizeof(int));
}

void MergeSort(int* array, int size)
{
  int* replace = (int*)malloc(sizeof(int) * size);
  if(replace == NULL){
    perror("malloc");
    exit(-1);
  }

  _MergeSort(array, 0, size - 1, replace);
  free(replace);
}

void MergeSortNonR(int* array, int size)
{
  int* sub = (int*)malloc(sizeof(int) * size);
  if(sub == NULL) {
    perror("malloc");
    exit(-1);
  }
  int gap = 1;
  while(gap < size){
    for(int i = 0; i < size; i += 2 * gap){
      int begin1 = i;
      int end1 = i + gap - 1;
      int begin2 = i + gap;
      int end2 = i + 2 * gap - 1;

      //end1 >= size
      //end2 >= size
      if(end1 >= size) break;
      if(end2 >= size) end2 = size - 1;

      //两个区间元素个数
      int sum = end2 - begin1 + 1;
      //当前元素位置
      int curr = begin1;
      while(begin1 <= end1 && begin2 <= end2){
        if(array[begin1] < array[begin2]) sub[curr++] = array[begin1++];
        else sub[curr++] = array[begin2++];
      }

      while(begin1 <= end1) sub[curr++] = array[begin1++];
      while(begin2 <= end2) sub[curr++] = array[begin2++];
      memcpy(array + i, sub + i, sum * sizeof(int));
    }
    gap *= 2;
  }
  free(sub);
}
